#!/usr/bin/python
# -*- coding: UTF-8 -*-

"""
    1.先对 nums2 中的每一个元素，求出它的右边第一个更大的元素；(单调栈)
    2.将上一步的对应关系放入哈希表（HashMap）中；
    3.再遍历数组 nums1，根据哈希表找出答案。
"""

class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        dict = {}
        stack = []
        for i in range(len(nums2)):
            while stack and nums2[i] > stack[-1]:
                dict[stack.pop()] = nums2[i]
            stack.append(nums2[i])
        res = []
        for j in nums1:
            res.append(dict.get(j,-1))
        print(res)
        return res

nums1 = [1,3,5,2,4]
nums2 = [6,5,4,3,2,1,7]
nums1 = [2,4]
nums2 = [1,2,3,4]
Solution().nextGreaterElement(nums1,nums2)


